P3611 Cow Dance Show S

题目描述

经过几个月的排练，奶牛们基本准备好展出她们的年度舞蹈表演。今年她们要表演的是著名的奶牛芭蕾——“cowpelia”。

表演唯一有待决定的是舞台的尺寸。一个大小为 $K$ 的舞台可以支持 $K$ 头牛同时在舞台上跳舞。在牛群中的 $N$ 头牛按照她们必须出现在舞蹈中的顺序方便地编号为 $1,2,...N$。第 $i$ 头牛计划跳 $d_i$ 的特定持续时间。
一开始，第 $1,2,...K$ 头牛出现在舞台上并开始跳舞。当这些牛中的某一头牛首先完成了她的部分，她会马上离开舞台并且第 $K+1$ 头牛会出现在舞台上并开始跳舞。所以，舞台上总有 $K$ 头奶牛在跳舞（直到表演的尾声，奶牛不够的时候）。当最后一头奶牛完成了她的舞蹈部分，表演结束，共花了 $T$ 个单位时间。

显然，$K$ 的值越大，$T$ 就越小。由于表演不能拖太长，你得知了指定 $T$ 的最大可能值的上限 $T_{max}$。请根据这个约束，确定 $K$ 的最小值。

输入格式

第一行包括 $N$ 和 $T_{max}$ 两个整数。

接下来的 $N$ 行，第 $i$ 行给出了第 $i$ 头牛跳舞的持续时间 $d_i$。第 $i$ 行包括一个整数 $d_i$。

保证 $K=N$ 时表演会按时完成。

$1\le N\le {10}^4$，$T_{max}\le {10}^6$，$1\le d_i\le {10}^5$。

输出格式

输出在表演时间不大于 $T_{max}$ 时的 $K$ 的最小可能值。

Solution

二分/优先队列/ 线段树

二分 +优先队列

到了最后只剩下 k 个时，取最大值即可。

void solve() {
    int n, t;cin >> n >> t;
    vector<int> a(n + 1);
    for (int i = 1;i <= n;i++)cin >> a[i];

    int kmi = 1, kma = n;
    while (kmi <= kma) {
        int kmid = (kmi + kma) / 2;
        int time = 0;
        priority_queue <int, vector<int>, greater<int>>q;
        for (int i = 1;i <= kmid;i++) {
            q.push(a[i]);
        }
        for (int i = kmid + 1;i <= n;i++) {
            int tmp = q.top();q.pop();
            q.push(a[i] + tmp);
        }
        while (q.size()) {
            time = q.top();q.pop();
        }
        if (time <= t) kma = kmid - 1;
        else kmi = kmid + 1;
    }
    cout << kmi << '\n';
}

二分 +线段树

(待更 $\dots$)